# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        
        ## 递归运行时间太大了
        #if n == 0:
        #    return 0
        #if n == 1:
        #    return 1
        
        #if n > 1:
        #    return self.Fibonacci(n-1) + self.Fibonacci(n-2)
        # write code here
        
        ## 使用动态规划
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        num_1 = 1
        num_2 = 1
        if n > 1:
            for i in range(n-2):
                temp = num_2
                num_2 = num_2 + num_1
                num_1 = temp
        return num_2